package com.qch.edu.lagou.algorithm.back;

/**
 * @Author qch
 * @Date 2021/7/23
 * N皇后问题--回溯算法（能用动态规划就不要用回溯）
 * N皇后问题的时间复杂度为：O(n!) 实际为n!/2
 *
 * 回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决
 */
public class NQueens {
    public static int QUEENS=8;//皇后数
    //下标是行，值是列
    int[] result=new int[QUEENS];//存储放好的皇后
    static int sum=0;
    //在指定行放皇后->递归
    public void setQueens(int row)
    {
        //从零开始
        if (row == QUEENS) {
            print();
            return;
        }
        //循环列
        for (int col = 0; col < QUEENS; col++) {
            if(isOK(row,col)){
                //存入数组
                result[row]=col;
                //开始下一行
                setQueens(row+1);
            }
        }
    }

    /**
     * 判断是否可以放置
     * @param row
     * @param col
     * @return
     */
    private boolean isOK(int row,int col)
    {
        int leftup=col-1;//左对角线
        int rightup=col+1;//右对角线
        for (int i = row-1; i>=0; i--) {
            //等于列-》原列存在
            if (result[i]==col)
            {
                return false;
            }
            //左对角线
            if(leftup>=0)
            {
                if(result[i]==leftup)
                    return false;
            }
            //右对角线
            if(rightup<8)
            {
                if(result[i]==rightup)
                    return false;
            }
            leftup--;
            rightup++;
            sum++;
        }
        return true;
    }
    /**
     * 打印结果
     */
    private void print(){
        for (int i = 0; i < result.length; i++) {
            //一行
            for (int j = 0; j < result.length; j++) {
                if(result[i]==j)
                {
                    System.out.print("Q|");
                }
                else {
                    System.out.print("*|");
                }
            }
            System.out.println();
        }
        System.out.println("-------------------------");
    }

    public static void main(String[] args) {
        NQueens nQueens=new NQueens();
        nQueens.setQueens(0);
        nQueens.print();
        System.out.println(sum);
        System.out.println(8*7*6*5*4*3*2*1);
    }
}
